package com.atguigu.gulimall.product.config;

import com.mysql.cj.x.protobuf.MysqlxCrud;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * ClassName: ListNode
 * Package： com.atguigu.gulimall.product.config
 * Description:
 *
 * @Author: Sweng
 * @Create: 2025/4/18 - 11:13
 * VERSION: version1.0
 **/
public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }

    public static void main(String[] args) {

        ListNode[] nodes = new ListNode[10];

        ListNode node3 = new ListNode(3);
        ListNode node6 = new ListNode(6);
        ListNode node9 = new ListNode(3);

        node3.next = node6;
        node6.next = node9;

        ListNode node2 = new ListNode(8);
        ListNode node4 = new ListNode(4);
        ListNode node8 = new ListNode(2);
        ListNode node10 = new ListNode(10);

        node2.next = node4;
        node4.next = node8;
        node8.next = node10;

        nodes[0] = node3;
        nodes[1] = node2;



        System.out.println(node3.toString());
       // System.out.println(reverseList(node1));
        //System.out.println(reverseKGroup(node1,1));
       // System.out.println(reverseBetween(node1,2,3));
//        System.out.println(mergekLists(nodes));
//        System.out.println(getLastKth(node3,2));
//        System.out.println(sortInListWithOther(node2));
        System.out.println(isPail(node3));

    }


    //反转连表
    public static ListNode reverseList(ListNode head) {

        if(head == null || head.next == null){
            return head;
        }

        ListNode cur = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return cur;
    }

    //连表指定区间反转m 到 n
    public static ListNode reverseBetween (ListNode head, int m, int n) {


        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode cur = head;

        for (int i = 0; i < m-1; i++) {
            cur = cur.next;
            pre = pre.next;
        }

        for (int i = 0; i < n-m; i++) {
            ListNode temp = cur.next;

            cur.next = cur.next.next;
            temp.next = pre.next;
            pre.next = temp;
        }

        return dummy.next;
    }

    //链表中接节每 K 反转
    public static ListNode reverseKGroup(ListNode head, int k){

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null){
            for (int i = 0; i<k && end!=null; i++) {
                end = end.next;
            }

            if(end == null){
                break;
            }
            ListNode next = end.next;
            ListNode start = pre.next;

            end.next = null;
            pre.next = reverseList(start);

            start.next = next;
            pre = start;
            end = start;
        }

        return dummy.next;
    }

    public static ListNode mergekLists(ListNode[] lists){

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        PriorityQueue<ListNode> listNodes = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if(o1.val > o2.val){
                    return 1;
                }else if(o1.val < o2.val){
                    return -1;
                }
                return 0;
            }
        });

        for(ListNode list : lists){
            if(list!=null)
                listNodes.offer(list);
        }

        while(!listNodes.isEmpty()){

            ListNode minNode = listNodes.poll();

            cur.next = minNode;
            cur = minNode;

            if(minNode.next != null)
                listNodes.offer(minNode.next);

        }
        return dummy.next;

    }

    //获取连表中 最后的k节点
    public static ListNode getLastKth(ListNode head,int k){

        ListNode start = head;
        ListNode end = head;

        for (int i = 0; i < k; i++) {
            end = end.next;
        }

        while (start!=null && end!=null){
            start =start.next;
            end = end.next;
        }

        return start;
    }

    //删除链表倒数第n个节点
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode start = dummy;
        ListNode curDel = head;
        ListNode end = head;

        for(int i=0;i<n;i++){
            end = end.next;
        }

        while(end!=null){

            start = curDel;
            curDel = curDel.next;
            end = end.next;

        }

        start.next = curDel.next;

        return dummy.next;

    }

    //两个链表找第一个公共节点
    public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        if (pHead1 == null || pHead2 == null)
            return null;

        ListNode startOne = pHead1;
        ListNode startTwo = pHead2;

        while (startOne != startTwo) {


            if (startOne == null) {
                startOne = pHead2;
            } else {
                startOne = startOne.next;
            }

            if (startTwo == null) {
                startTwo = pHead1;
            } else {
                startTwo = startTwo.next;
            }


        }

        return startOne;

    }

    //两个链表相加 逆向连表相加 使用堆栈排序链表。

    /**
     * 使用一个中间保存 进位符号。
     * @param head1
     * @param head2
     * @return
     */

    public static ListNode addInList (ListNode head1, ListNode head2) {
        // write code here

        ListNode dummy = new ListNode(-1);
        int cal = 0;

        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        Stack<Integer> result = new Stack<>();

        while(head1 !=null){
            s1.push(head1.val);
            head1 = head1.next;
        }

        while(head2 !=null){
            s2.push(head2.val);
            head2 = head2.next;
        }

        while(!s1.isEmpty() && !s2.isEmpty()){

            int resultNum = s1.pop() + s2.pop() + cal;

            if(resultNum >9){
                result.push(resultNum%10);
                cal = 1;
            }else{
                result.push(resultNum);
                cal = 0;
            }
        }

        while(!s1.isEmpty()){

            int resultNum = s1.pop() + cal;
            if(resultNum >9){
                result.push(resultNum%10);
                cal = 1;
            }else{
                result.push(resultNum);
                cal = 0;
            }

        }

        while(!s2.isEmpty()){

            int resultNum = s2.pop() + cal;
            if(resultNum >9){
                result.push(resultNum%10);
                cal = 1;
            }else{
                result.push(resultNum);
                cal = 0;
            }

        }

        ListNode head = dummy;
        while(!result.isEmpty()){
            ListNode x = new ListNode(result.pop());
            head.next = x;
            head = head.next;
        }

        return dummy.next;

    }

    /**
     *  简单排序  使用连表
     */
    public ListNode sortInList (ListNode head) {
        // write code here

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        //设后前置头检点
        ListNode cur = dummy;
        while(cur.next != null){

            //前置移动排序
            ListNode preSortNode = cur;
            //移动排序
            ListNode sortNode = cur.next;

            //最小值
            ListNode min = null;
            //最小值前置
            ListNode preMin = null;

            while(sortNode !=null){
                if(min == null || min.val > sortNode.val){
                    //记录最小值
                    min = sortNode;
                    preMin = preSortNode;
                }
                //移动节点
                preSortNode = preSortNode.next;
                sortNode = sortNode.next;
            }

            //最小值不是当前节点，则移动到前面
            if(min != cur){
                //断开最小值。 连接最小值前置节点。 和最小值后置节点
                preMin.next = min.next;

                //最小值后置节点 连接当前遍历节点的后置
                min.next = cur.next;

                //遍历节点连接最小值节点
                cur.next = min;

                //遍历节点移动到最小值节点继续循环。
                cur = min;
            }


        }

        return dummy.next;
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
        ListNode dummy = new ListNode(-1);

        // 设置一个指针，指向虚拟节点
        ListNode pre = dummy;

        // 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
        while (l1 != null && l2 != null) {
            // 如果 l1 当前节点的值小于等于了 l2 当前节点的值
            if (l1.val <= l2.val) {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l1
                pre.next = l1;
                // 让 l1 向后移动
                l1 = l1.next;
            }else {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l2
                pre.next =l2;
                // 让 l2 向后移动
                l2 = l2.next;
            }
            // 让 pre 向后移动
            pre = pre.next;
        }

        // 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
        // 直接把剩下的节点加入到 pre 的 next 指针位置

        // 如果 l1 中还有节点
        if (l1 != null) {
            // 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l1;
        }

        // 如果 l2 中还有节点
        if (l2 != null) {
            // 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l2;
        }

        // 最后返回虚拟节点的 next 指针
        return dummy.next;
    }

    public static ListNode sortInListWithOther (ListNode head) {
        // write code here
        int length = 0;

        ListNode node = head;

        while(node != null){

            length++;
            node = node.next;
        }

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        for(int subLength = 1;subLength < length; subLength *= 2){

            ListNode prev = dummyHead;
            ListNode curr = dummyHead.next;

            while(curr != null){

                ListNode head1 = curr;

                for(int i = 1; i<subLength && curr.next != null ; i++){
                    curr = curr.next;
                }

                ListNode head2 = curr.next;
                curr.next = null;

                curr = head2;
                for(int i = 1; i<subLength && curr != null ; i++){
                    curr = curr.next;
                }

                ListNode next = null;

                if(curr !=null){
                    next = curr.next;
                    curr.next = null;
                }

                ListNode merged = mergeTwoLists(head1, head2);

                prev.next = merged;
                while(prev.next != null){
                    prev = prev.next;
                }

                curr = next;
            }
        }
        return dummyHead.next;
    }


    public static boolean isPail (ListNode head) {

        if(head.next == null){
            return true;
        }
        // write code here

        ListNode cur = head;

        ListNode middler = isMiddler(cur);

        ListNode revNode = reverseList(middler.next);

        ListNode a = head;
        boolean flag = true;

        while(flag && revNode !=null){

            if(a.val != revNode.val){
                flag = false;
            }
            a = a.next;
            revNode = revNode.next;
        }

        return flag;
    }

    public static ListNode isMiddler(ListNode node){
        ListNode fast = node;
        ListNode slow = node;

        while(slow.next !=null &&(fast.next!=null && fast.next.next!=null)){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    /**
     * 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
     * 注意是节点的编号而非节点的数值
     *
     * 设置两个 一个奇链表 一个偶链表 一个偶数链表头。
     *
     */
    public static ListNode oddEvenList (ListNode head) {
        // write code here
        if(head == null)
            return null;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        //奇数
        ListNode odd = head;
        //偶数
        ListNode even = head.next;

        ListNode evenHead = head.next;

        while(odd.next != null && even.next != null){

            odd.next = even.next;
            odd = odd.next;

            even.next = odd.next;
            even = even.next;
        }

        odd.next = evenHead;

        return dummy.next;
    }

    //删除链表中重复的元素
    public static ListNode deleteDuplicates (ListNode head) {
        if(head == null)
            return null;
        // write code here

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode cur = head;
        ListNode after = head.next;

        while(cur.next !=null){
            if(cur.val == after.val){
                cur.next = after.next;
                after = after.next;
            }else{
                cur = cur.next;
                after = after.next;
            }
        }
        return dummy.next;
    }

    /**
     *
     给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

     注意这里的  cur.next 和 cur.next.next 显示引用不能使用对象操作。

     */

    public static ListNode deleteDuplicatesTwo (ListNode head) {
        // write code here
        if(head == null)
            return null;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;

        while(cur.next !=null && cur.next.next!=null ){
            if(cur.next.val == cur.next.next.val){
                int value = cur.next.val;
                while(cur.next != null && cur.next.val == value){
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }

        return dummy.next;
    }


}





